
# 63. 不同路径 II


def uniquePathsWithObstacles(obstacleGrid):
    """
    :type obstacleGrid: List[List[int]]
    :rtype: int
    """
    hang = len(obstacleGrid)
    lie = len(obstacleGrid[0])
    if hang == 1:
        for i in range(0, lie):
            if obstacleGrid[0][i] == 1:
                return 0
        return 1
    if lie == 1:
        for j in range(0, hang):
            if obstacleGrid[j][0] == 1:
                return 0
        return 1
    dp = [[None] * lie for _ in range(hang)]
    temp1 = hang
    temp2 = lie
    for i in range(0, hang):
        if obstacleGrid[i][0] == 1:
            temp1 = i
            break
        dp[i][0] = 1
    for i in range(temp1, hang):
        dp[i][0] = 0
    for i in range(0, lie):
        if obstacleGrid[0][i] == 1:
            temp2 = i
            break
        dp[0][i] = 1
    for i in range(temp2, lie):
        dp[0][i] = 0
    for i in range(1, hang):
        for j in range(1, lie):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    print(dp)
    return dp[hang - 1][lie - 1]

if __name__ == "__main__":
    result = uniquePathsWithObstacles([[0,0],[1,1],[0,0]])
    print(result)